UVa/10036 - Divisibility/10036.3.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <stdio.h>
   5
   6 const int MAXN = 10000, MAXK = 100;
   7
   8 bool dp[MAXN][MAXK];
   9
  10 int main(){
  11   int cases;
  12   scanf("%d", &cases);
  13   while (cases--){
  14     int n, k;
  15     scanf("%d %d", &n, &k);
  16     int a[n];
  17     for (int i=0; i<n; ++i){
  18       for (int j=0; j<k; ++j){
  19         dp[i][j] = false;
  20       }
  21       scanf("%d", &a[i]);
  22     }
  23
  24     if (a[0] < 0) a[0] *= -1;
  25     dp[0][a[0]%k] = true;
  26     for (int i=0; i<n-1; ++i){
  27       for (int j=0; j<k; ++j){
  28         if (dp[i][j]){
  29           int t = j + a[i+1];
  30           if (t < 0) t *= -1;
  31           dp[i+1][t%k] = true;
  32
  33           t = j - a[i+1];
  34           if (t < 0) t *= -1;
  35           dp[i+1][t%k] = true;
  36         }
  37       }
  38     }
  39
  40     printf((dp[n-1][0]?"D":"Not d"));
  41     puts("ivisible");
  42   }
  43   return 0;
  44 }